package com.example.demo.leetcode.top100;

import java.util.Arrays;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _98颜色分类
 * @description
 * @date 2023/07/04 14:44
 * <p>
 * ******************************************************
 */
public class _98颜色分类 {


    /**
     * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，
     * 原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     * <p>
     * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     * <p>
     * 必须在不使用库内置的 sort 函数的情况下解决这个问题。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [2,0,2,1,1,0]
     * 输出：[0,0,1,1,2,2]
     * 示例 2：
     * <p>
     * 输入：nums = [2,0,1]
     * 输出：[0,1,2]
     * <p>
     * <p>
     * 提示：
     * <p>
     * n == nums.length
     * 1 <= n <= 300
     * nums[i] 为 0、1 或 2
     *
     * @param nums
     */
    public void sortColors1(int[] nums) {
        int length = nums.length;
        int num_1 = 0;
        int num_2 = 0;
        for (int i = 0; i < length; i++) {
            if (nums[i] == 1) {
                num_1++;
            } else if (nums[i] == 2) {
                num_2++;
            }
            nums[i] = 0;
        }

        int num_0 = length - num_1 - num_2;

        for (int i = num_0; i < num_1 + num_0; i++) {
            nums[i] = 1;
        }
        for (int i = num_0 + num_1; i < length; i++) {
            nums[i] = 2;
        }
    }

    public void sortColors(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] nums, int start, int end) {
        if (start >= end || start < 0 || end >= nums.length) {
            return;
        }
        int match = nums[start];
        int left = start;
        int right = end;
        while (left <= right) {
            if (nums[left] > match) {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                right--;
            } else {
                left++;
            }
        }

        int temp = nums[start];
        nums[start] = nums[left - 1];
        nums[left - 1] = temp;

        quickSort(nums, start, left - 2);
        quickSort(nums, left, end);
    }

    public static void main(String[] args) {
        int[] nums = {2, 0, 2, 1, 1, 0};
        _98颜色分类 s = new _98颜色分类();
        s.sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }

}
